package Hot100;

import common.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-12-26 13:47
 */
public class numTrees96 {

    /**96. 不同的二叉搜索树
     * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
     * 递归：计算以每个节点为根节点的BST的个数
     * */
    HashMap<String,Integer> memo;
    //count计算[left,right]可以构成BST的个数
    int count(int left,int right){
        if (left>right) return 1;
        String key=left+","+right;
        if (memo.containsKey(key)){
            return memo.get(key);
        }
        int res=0;
        for (int i = left; i <= right; i++) {
            res+=count(left,i-1)*count(i+1,right);
        }
        memo.put(key,res);
        return res;
    }
    public int numTrees(int n) {
        memo=new HashMap<>();
        return count(1,n);
    }

    /**95. 不同的二叉搜索树 II
     * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
     * 递归：以每个节点为根节点构造BST,递归构造出左子树的列表和右子树的列表，然后将其排列组合
     * */
    List<TreeNode> build(int left,int right){
        List<TreeNode> res=new LinkedList<>();
        if (left>right){
            res.add(null);
            return res;
        }
        for (int i = left; i <=right ; i++) {
            List<TreeNode> leftRoot = build(left, i - 1);
            List<TreeNode> rightRoot = build(i + 1, right);
            for (int j = 0; j < leftRoot.size(); j++) {
                for (int k = 0; k < rightRoot.size(); k++) {
                    TreeNode root=new TreeNode(i);
                    root.left=leftRoot.get(j);
                    root.right=rightRoot.get(k);
                    res.add(root);
                }
            }
        }
        return res;
    }
    public List<TreeNode> generateTrees(int n) {
        return build(1,n);
    }
}
